package com.demo.java.OD151_200.OD167;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【删除指定目录】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145779964
 */
public class OdMain {
    private static final Map<Integer, List<Integer>> tree = new TreeMap<>();

    public static void main(String[] args) {
        List<Integer> parents = new ArrayList<>();
        List<Integer> nodes = new ArrayList<>();
        try (Scanner s = new Scanner(System.in)) {
            int num = s.nextInt();  // 读取节点的数量
            for (int i = 0; i < num; ++i) {
                nodes.add(s.nextInt());  // 读取每个节点ID
                parents.add(s.nextInt());  // 读取每个节点的父节点ID
            }
            int rmId = s.nextInt();  // 读取要删除的节点ID
            buildTree(parents, nodes);  // 根据父子关系构建树
            rmNode(rmId);  // 删除指定的节点及其子节点
            tree.keySet().forEach(e -> System.out.print(e + " "));  // 输出剩余节点ID
            System.out.println();
        }
    }

    // 构建树形结构，父节点为key，子节点为value
    public static void buildTree(List<Integer> parent, List<Integer> node) {
        for (int i = 0; i < node.size(); ++i) {
            Integer nodeKey = node.get(i);
            Integer parentKey = parent.get(i);
            tree.putIfAbsent(nodeKey, new ArrayList<>());
            if (!parentKey.equals(0)) {  // 父节点为0表示根节点，跳过根节点
                List<Integer> parentList = tree.computeIfAbsent(parentKey, k -> new ArrayList<>());
                parentList.add(nodeKey);  // 将子节点加入到父节点的子节点列表中
            }
        }
    }

    // 删除指定节点及其所有子节点
    public static void rmNode(Integer node) {
        List<Integer> children = tree.get(node);
        if (children == null) {
            return;  // 如果该节点没有子节点，直接返回
        }
        if (children.size() == 0) {
            tree.remove(node);  // 删除没有子节点的节点
            return;
        }
        children.forEach(child -> rmNode(child));  // 递归删除子节点
        tree.remove(node);  // 删除当前节点
    }
}